package LeetCode1;

//二叉树的最近公共祖先
public class Num236 {
    private TreeNode lca;

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        findNode(root, p, q);
        return lca;
    }

    private boolean findNode(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return false;
        }
        //分别从左右子树开始找，找到最少一个即为真
        int left = findNode(root.left, p, q) ? 1 : 0;
        int right = findNode(root.right, p, q) ? 1 : 0;
        //找到一个节点
        int mid = (root == p || root == q) ? 1 : 0;
        if (mid + left + right == 2) {
            //这里边有三种情况，
            //mid + left / right = 2，此时说明当前节点既是要找的节点也是最近祖先节点
            //left + right = 2，此时说明当前节点之下的此节点包含了两个要找的节点，该节点为最近祖先节点
            lca = root;
        }
        //有一个为找到的就为真
        return (mid + right + left) > 0;
    }
}
